

In [ ]:

    
%%HTML
<style>
.container { width:100% }
</style>

The function fib takes a natural number $n$ as argument. The expression $\texttt{fib}(n)$ computes the $n$-th Fibonacci number.



In [ ]:

    
def fib(n):
    if n < 2:
        return n
    return fib(n-2) + fib(n-1)



In [ ]:

    
for n in range(15):
    print(f'fib({n}) = {fib(n)}')



In [ ]:

    
%%time
fib(33)

The function memoize takes a function f as its argument. It returns a memoized version of the function f. This memoized version will store all results in a cache and look them up instead of recomputing them.



In [ ]:

    
def memoize(f):
    Cache = {}
    
    def f_memoized(*args):
        if (f, args) in Cache:
            return Cache[(f, args)]
        result = f(*args)
        Cache[(f, args)] = result
        return result
    
    return f_memoized



In [ ]:

    
fib = memoize(fib)



In [ ]:

    
%%time
fib(33)



In [ ]:

    
%%time
fib(33)



In [ ]:

    
@memoize
def fib2(n):
    if n < 2:
        return n
    return fib2(n-2) + fib2(n-1)



In [ ]:

    
%%time
fib2(33)



In [ ]:

    
fib.__closure__[0].cell_contents



In [ ]: